//LinkList.h
#include"List.h"
#include"LinkNode.h"

//定义单链表类
template <class ElemType>
class LinkList :public List<ElemType>
{
public:
	LinkList();
	LinkList(const LinkList<ElemType>&);
	~LinkList();
	bool IsEmpty() const { return len <= 0; }
	int Length() const { return len; }
	void Clear();
	bool GetElem(ElemType&, int) const;
	bool SetElem(const ElemType&, int);
	int LocateElem(const ElemType&) const;
	int LocatePrior(const ElemType&) const;
	int LocateNext(const ElemType&) const;
	bool Insert(const ElemType&, int);
	bool Append(const ElemType&);
	bool Delete(ElemType&, int );
	bool Inverse();
	void Traverse(void(*visit)(const ElemType&e)) const;
	LinkList<ElemType> & operator=(const LinkList<ElemType>&);
private:
	int len;
	LinkNode<ElemType>* head;
	LinkNode<ElemType>* tail;
	void CopyFrom(const LinkList<ElemType>&);
};

//默认构造函数
template<class ElemType>
LinkList<ElemType>::LinkList()
{
	len = 0;
	head = tail = new LinkNode<ElemType>;
	head->next = NULL;
}

//拷贝构造函数
template<class ElemType>
LinkList<ElemType>::LinkList(const LinkList<ElemType> &r)
{
	CopyFrom(r);
}

//析构函数
template<class ElemType>
LinkList<ElemType>::~LinkList()
{
	Clear();
	delete head;
}

//置表为空
template<class ElemType>
void LinkList<ElemType>::Clear()
{
	LinkNode<ElemType>* p = head->next, * q;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	tail = head;
	head->next = NULL;
	len = 0;
}

//在i的位置存入数据
template<class ElemType>
bool LinkList<ElemType>::GetElem(ElemType& e, int i) const
{
	if (i<1 || i>len)
		return false;
	LinkNode<ElemType>* p = head->next;
	int k = 1;
	while (k < i) {
		p = p->next;
		k++;
	}
	e = p->data;
	return true;
}

//在第i个位置存入数据
template<class ElemType>
bool LinkList<ElemType>::SetElem(const ElemType &e, int i)
{
	if (i<1 || i>len)
		return false;
	LinkNode<ElemType>* p = head->next;
	int k = 1;
	while (k<i)
	{
		p = p->next;
		k++;
	}
	p->data = e;
	return true;
}

//查找符合条件的数据元素的位置
template<class ElemType>
int LinkList<ElemType>::LocateElem(const ElemType &e) const
{
	int i=1;
	LinkNode<ElemType>* p = head->next;
	while (p&&p->data!=e)
	{
		i++;
		p = p->next;
	}
	if (p)
		return i;
	return 0;
}

//查找符合条件的数据元素的位置的前驱
template<class ElemType>
int LinkList<ElemType>::LocatePrior(const ElemType &e) const
{
	int i = LocateElem(e);
	if (i > 1)
		return i - 1;
	else
		return 0;
}

//查找符合条件的数据元素的位置的后继
template<class ElemType>
int LinkList<ElemType>::LocateNext(const ElemType &e) const
{
	int i = LocateElem(e);
	if (i >= 1 && i<len)
		return i + 1;
	else
		return 0;
}

//在第i个结点之前插入新的数据元素e
template<class ElemType>
bool LinkList<ElemType>::Insert(const ElemType &e, int i)
{
	LinkNode<ElemType>* p, * q;
	int k = 1;

	if (i<1 || i>len + 1)
		return false;
	q = new LinkNode<ElemType>;
	q->data = e;
	p = head;
	while (k<i)
	{
		p = p->next;
		k++;
	}
	q->next = p->next;
	p->next = q;
	
	if (i == len + 1)
		tail = q;
	++len;
	return true;
}

//在表中末尾插入新元素e
template<class ElemType>
bool LinkList<ElemType>::Append(const ElemType& e)
{
	LinkNode<ElemType>* q;
	q = new LinkNode<ElemType>;
	q->data = e;
	tail->next = q;
	tail = q;
	tail->next = NULL;
	++len;
	return true;
}

//在单链表中删除第i个节点
template<class ElemType>
bool LinkList<ElemType>::Delete(ElemType&e, int i)
{
	if (i<1 || i>len)
		return false;

	LinkNode<ElemType>* p, * q;
	int k = 1;
	p = head;
	while (k<i)
	{
		p = p->next;
		k++;
	}
	q = p->next;
	p->next = q->next;

	if (q == tail)
		tail = p;
	e = q->data;
	delete q;
	--len;
	return true;
}

//遍历
template<class ElemType>
void LinkList<ElemType>::Traverse(void(*visit)(const ElemType& e)) const
{
	LinkNode<ElemType>* p = head->next;
	while (p)
	{
		visit(p->data);
		p = p->next;
	}
}

//重载
template<class ElemType>
LinkList<ElemType>& LinkList<ElemType>::operator=(const LinkList<ElemType>&r)
{
	Clear();
	delete head;
	CopyFrom(r);
	return *this;
	// TODO: 在此处插入 return 语句
}

//拷贝函数
template<class ElemType>
void LinkList<ElemType>::CopyFrom(const LinkList<ElemType>&r)
{
	len = 0;
	head = tail = new LinkNode<ElemType>;
	head->next = NULL;
	LinkNode<ElemType>* p = r.head->next;
	while (p)
	{
		Append(p->data);
		p = p->next;
	}
}

//倒置
template<class  ElemType> 
bool  LinkList<ElemType> :: Inverse ( ) 
{    
     if ( head->next == NULL ) return false;
     LinkNode<ElemType>  *p = head->next, *pr;
     head->next=NULL; 
     while ( p != NULL ) 
     {  pr = p;  p = p->next; 
        pr->next = head->next;  
        head->next = pr;   
     }
     return true;   
}